#include<assert.h>
#include<iostream>
using namespace std;
template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}

	AVLTreeNode<T>* _pLeft;
	AVLTreeNode<T>* _pRight;
	AVLTreeNode<T>* _pParent;
	T _data;
	int _bf;   // 节点的平衡因子
};



// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	AVLTree()
		: _pRoot(nullptr)
	{}

	//中序
	void InOrder()
	{
		_InOrder(_pRoot);
		cout << endl;
	}

	// 在AVL树中插入值为data的节点
	bool Insert(const T& data)
	{
		if (_pRoot == nullptr)
		{
			_pRoot = new Node(data);
			return true;
		}

		Node* cur = _pRoot;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_data < data)
			{
				parent = cur;
				cur = cur->_pRight;
			}
			else if (cur->_data > data)
			{
				parent = cur;
				cur = cur->_pLeft;
			}
			else
			{
				return false;
			}
		}
		//找到插入点
		cur = new Node(data);
		if (parent->_data < data)
			parent->_pRight = cur;
		else
			parent->_pLeft = cur;

		cur->_pParent = parent;

		//调整平衡因子
		while (parent)
		{
			//左减右加
			if (cur == parent->_pLeft) parent->_bf--;

			else  parent->_bf++;

			if (parent->_bf == 0) //加入前bf -1 \ 1
				break;

			else if (parent->_bf == 1 || parent->_bf == -1)  //bf==0 ,继续向上调整
			{
				cur = cur->_pParent;
				parent = parent->_pParent;
			}

			else if (parent->_bf == -2 || parent->_bf == 2)
			{
				//右边高，左单旋
				if (parent->_bf == 2 && cur->_bf == 1)
					RotateL(parent);

				//左边高，右单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
					RotateR(parent);

				//折线形 ,先左旋
				else if (parent->_bf == 2 && cur->_bf == -1)
					RotateRL(parent);

				else if (parent->_bf == -2 && cur->_bf == 1)
					RotateLR(parent);
			}

			else
					assert(false);

			}
	}

	// AVL树的验证
	bool IsAVLTree()
	{
		return _IsAVLTree(_pRoot);
	}

private:
	// 根据AVL树的概念验证pRoot是否为有效的AVL树
	bool _IsAVLTree(Node* pRoot)
	{
		if (pRoot == nullptr)
			return true;
		size_t Lh = _Height(pRoot->_pLeft);
		size_t Rh = _Height(pRoot->_pRight);
		int diff = Rh - Lh;
		if (diff!=pRoot->_bf)
		{
			cout << pRoot->_data << ":" << "结点异常" << endl;
				return false;
		}

		return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);

	}
	size_t _Height(Node* pRoot)
	{
		if (pRoot == nullptr)
		{
			return 0;
		}
		size_t LHight = _Height(pRoot->_pLeft);
		size_t RHight = _Height(pRoot->_pRight);
		return LHight > RHight ? LHight + 1 : RHight + 1;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_pLeft);
		cout << "data:" << root->_data << " " << "bf:" << root->_bf << endl;
		_InOrder(root->_pRight);
		IsAVLTree();
	}
	// 右单旋
	void RotateR(Node* pParent)
	{
		Node* subL = pParent->_pLeft;
		Node* subLR = subL->_pRight;
		Node* parentparent = pParent->_pParent;

		pParent->_pLeft = subLR;
		if (subLR)
			subLR->_pParent = pParent;

		subL->_pRight = pParent;
		pParent->_pParent = subL;

		if (pParent == _pRoot)
		{
			_pRoot = subL;
			subL->_pParent = nullptr;
		}
		else
		{
			if (parentparent->_pLeft == pParent)
				parentparent->_pLeft = subL;
			else
				parentparent->_pRight = subL;

			subL->_pParent = parentparent;
		}
		//更新平衡因子
		subL->_bf = pParent->_bf = 0;
	}

	// 左单旋
	void RotateL(Node* pParent)
	{
		Node* subR = pParent->_pRight;
		Node* subRL = subR->_pLeft;
		Node* parentparent = pParent->_pParent;
		
		//链接subrl
		pParent->_pRight = subRL;
		if (subRL)
			subRL->_pParent = pParent;

		subR->_pLeft = pParent;
		pParent->_pParent = subR;

		if (pParent == _pRoot)
		{
			_pRoot = subR;
			_pRoot->_pParent = nullptr;
		}
		else
		{
			//判断parentparent的孩子
			if (parentparent->_pLeft == pParent)
				parentparent->_pLeft = subR;

			else
				parentparent->_pRight = subR;
			
			subR->_pParent = parentparent;
		}
		//更新平衡因子
		pParent->_bf = subR->_bf = 0;


	}
	// 右左双旋
	void RotateRL(Node* pParent)
	{
		Node* subR = pParent->_pRight;
		Node* subRL = subR->_pLeft;
		int bf = subRL->_bf;
		RotateR(subR);
		RotateL(pParent);

		//更新平衡因子
		if (bf == 0)
			subR->_bf = subRL->_bf = pParent->_bf = 0;

		else if (bf == -1)
		{
			pParent->_bf = subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)
		{
			pParent->_bf = -1;
			subRL->_bf = subR->_bf = 0;
		}
		else
			assert(false);
	}


	// 左右双旋
	void RotateLR(Node* pParent)
	{
		Node* subL = pParent->_pLeft;
		Node* subLR = subL->_pRight;
		int bf = subLR->_bf;

		RotateL(subL);
		RotateR(pParent);

		//调整平衡因子
		if (bf == 0)
		{
			subL->_bf = subLR->_bf = pParent->_bf = 0;
		}

		else if (bf == -1)
		{
			subL->_bf = subLR->_bf = 0;
			pParent->_bf = 0;
		}

		else if (bf == 1)
		{
			pParent->_bf = subLR->_bf = 0;
			subL->_bf = -1;
		}

		else
			assert(false);

	}
private:
	Node* _pRoot;
};
